1. Field
The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns an implementation of a mutual exclusion mechanism known as “read-copy update” in a computing environment wherein processors that need to perform callback processing are capable of assuming low power states.
2. Description of the Prior Art
By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will see the effect of the update operation by encountering B′ as they dereference B's pointer. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference( ) primitive.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader process is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch.
In FIG. 3, four tasks 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks 0, 1, 2, and 3 were reader tasks traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater.
Grace periods may synchronous or asynchronous. According to the synchronous technique, an updater performs the first phase update operation, blocks (waits) until a grace period has completed, and then implements the second phase update operation, such as by removing stale data. According to the asynchronous technique, an updater performs the first phase update operation, specifies the second phase update operation as a callback, then resumes other processing with the knowledge that the callback will eventually be processed at the end of a grace period. Advantageously, callbacks requested by one or more updaters can be batched (e.g., on callback lists) and processed as a group at the end of an asynchronous grace period. This allows asynchronous grace period overhead to be amortized over plural deferred update operations.
More recently, RCU grace period processing has been adapted to account for processor low power states (such as, on Intel® processors, the C1E halt state, or the C2 or deeper halt states). Operating systems can take advantage of low power state capabilities by using mechanisms that withhold regular timer interrupts from processors (in a low power state) unless the processors need to wake up to perform work. The dynamic tick framework (also called “dyntick” or “nohz”) in recent versions of the Linux® kernel is one such mechanism. In recent RCU implementations designed for low power applications in the Linux® kernel, the scheduler places a processor in dyntick-idle mode using a function called “tick_nohz_stop_sched_tick( ).” Before actually changing the processor's mode, this function invokes another function called “rcu_needs_cpu( )” to check whether the processor has any callback processing work that needs to be performed, even if none needs to be done immediately. Historically, if the processor had pending callbacks, it was not permitted to enter dyntick-idle mode. The reason for this is because grace period and callback detection processing is normally driven by the scheduling clock interrupt, and such processing will not be performed when the scheduling clock tick is suppressed. Unfortunately, keeping the processor out of dyntick-idle mode to wait for callbacks to be invoked can cause the processor to remain in a high-power mode for many milliseconds following the time its power level could have otherwise been reduced.
Commonly-owned U.S. patent application Ser. No. 13/225,425, filed on Sep. 3, 2011 (hereinafter the '425 application), discloses a technique that improves upon the foregoing processing by modifying the rcu_needs_rcu( ) function in order to provide an energy efficient read-copy update implementation for light workloads running on systems with many processors, or for workloads that generate many RCU callbacks. In the Linux® kernel, an embodiment of the disclosed technique is implemented by the RCU_FAST_NO_HZ configuration option. According to the disclosed technique, when an operating system scheduler attempts to place a processor in dyntick-idle mode (or some other low power state that withholds scheduling clock interrupts), the modified rcu_needs_cpu( ) function does several things. During an initial hold-off period, the rcu_needs_cpu( ) function notes if the processor has pending callbacks and returns without the processor being placed in dyntick-idle mode, reporting the callback status to the caller. Once the hold-off period is over, the processor will be prevented from entering a low power state only in the event that there are one or more RCU callbacks that are ready for invocation, or if the processor needs to perform an action that helps advance RCU's grace period machinery and there are also one or more pending callbacks (even if they are not ready to be invoked). In either case, an operation known as callback flush loop processing will be performed for a specified number of passes. This processing results in alternating attempts to (1) advance the RCU grace period machinery and (2) process the callbacks in a clean environment (such as the Linux® kernel's softirq context). In particular, a function called “rcu_process_callbacks( )” is invoked within the softirq environment to advance the callbacks on the callback lists and process any that are ready to be invoked. At the end of callback processing, the rcu_process_callbacks( ) function re-invokes the rcu_needs_cpu( ) function, which then causes the rcu_process_callbacks( ) function to be re-invoked in a separate softirq context, and so on, until there are (hopefully) no callbacks. Each hand off between the rcu_needs_cpu( ) function (initially called by the scheduler attempting to place a processor in dyntick-idle mode) and the rcu_process_callbacks( ) function (called within softirq context) represents one pass through the callback flush loop. Callback flush loop processing is continued for a specified number of passes (e.g., five) or until all of the processor's callbacks have been processed (whichever occurs sooner). If the callback flush operations are successful at removing all pending callbacks within a specified number of passes through the loop, the processor will be placed in dyntick-idle mode.
The technique disclosed in the '425 application allows a processor to be placed in a low power state even if there are pending RCU callbacks, provided none require immediate invocation and the processor is not needed for grace period advancement processing. Under this condition, callbacks that will not be ready for invocation until one or more grace periods in the future will not prevent a processor from entering a low power state. Such pending callbacks will merely be noted so that the processor can be subsequently reawakened when the callbacks become ready. This can be done by setting a per-processor callback flag (which may be given a name such as “rcu_have_callbacks”) that is cleared when the callbacks are eventually processed or when the processor leaves its low power state.
The number of passes through the callback flush loop, as well as the hold-off period that is observed before entering the loop, may be selected using per-processor state variables. When RCU ends a grace period, a check may be performed to see if there are any other low power state processors with their rcu_have_callbacks flag set. If so, the corresponding processors may be sent interprocessor interrupts (IPIs) to force them out of their low power state to process their callbacks.
Although the technique disclosed in the '425 application works well, the Linux® kernel's RCU API can now reliably detect transitions of tasks to and from the idle loop. This allows the decision making rules implemented by rcu_needs_cpu( ) to be relaxed in favor of allowing low power states to be entered more frequently. Also, the use of IPIs to awaken low power state processors to perform RCU processing at the end of grace periods can result in undesirable overhead if the target processor was already awakened for some other reason. Finally, applicant has determined that it would be desirable to address a design feature of current implementations of the Linux® kernel that restricts RCU to processing a limited number of RCU callbacks at a time (e.g., 10) unless there is an excessive number of RCU callbacks to be processed (e.g., 10,000 or more). This restriction is useful for limiting RCU's impact on scheduling latency, but applicant submits that such limiting may not always be necessary. What is needed is a way for RCU to determine when there is no latency penalty for invoking larger batches of RCU callbacks at a time.